package com.shm.leetcode;

/**
 * 765. 情侣牵手
 * N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
 *
 * 人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
 *
 * 这些情侣的初始座位  row[i] 是由最初始坐在第 i 个座位上的人决定的。
 *
 * 示例 1:
 *
 * 输入: row = [0, 2, 1, 3]
 * 输出: 1
 * 解释: 我们只需要交换row[1]和row[2]的位置即可。
 * 示例 2:
 *
 * 输入: row = [3, 2, 0, 1]
 * 输出: 0
 * 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
 * 说明:
 *
 * len(row) 是偶数且数值在 [4, 60]范围内。
 * 可以保证row 是序列 0...len(row)-1 的一个全排列。
 * @author SHM
 */
public class MinSwapsCouples {
    /**
     * 题意解读：
     *
     * 一对情侣，两个座位，无须交换就可以牵手成功。
     *
     *
     *
     * 两对情侣，如下图所示的时候，最少须要交换 11 次。
     *
     *
     *
     * 三对情侣，如果不能够彼此牵手，只可能出现下面这种 首尾相连 的情况。
     *
     *
     *
     * 四对情侣、五对情侣以上的情况也可以类似看待。通过举例，可以知道把 坐错了位置、逻辑上连在一起的情侣 拆成所有的情侣都能彼此牵手的 「最少交换次数 = 情侣对数 - 1」。
     *
     * 方法：并查集
     * 「首尾相连」这件事情可以使用 并查集 表示，将输入数组相邻位置的两个 编号 在并查集中进行合并。编写代码基于了下面的事实：
     *
     * 如果一对情侣恰好坐在了一起，并且坐在了成组的座位上，其中一个下标一定是偶数，另一个一定是奇数，并且「偶数的值 + 1 = 奇数的值」。例如编号数对 [2, 3]、[9, 8]，这些数对的特点是除以 22（下取整）得到的数相等。
     *
     * 输出是什么？
     * 要求出「最少交换次数」。假设一共有 NN 对情侣，逻辑上连在了一起的情侣（包括坐错位置和坐对位置的情况）分别有 N_1,N_2,\cdots,N_nN
     * 1
     * ​
     *  ,N
     * 2
     * ​
     *  ,⋯,N
     * n
     * ​
     *   对，这里 nn 是并查集里连通分量的个数，并且 N_1 + N_2 + \cdots N_n = NN
     * 1
     * ​
     *  +N
     * 2
     * ​
     *  +⋯N
     * n
     * ​
     *  =N。把逻辑上连在一起的情侣拆开，每一个连通分量至少须要 N_1 - 1,N_2 - 1,\cdots,N_n - 1N
     * 1
     * ​
     *  −1,N
     * 2
     * ​
     *  −1,⋯,N
     * n
     * ​
     *  −1 次。
     *
     *
     *
     * 这种规律对于初始的时候已经坐在一起的情侣同样成立，因为已经坐在一起的情侣在并查集里成为一个连通分量，无须交换，此时 1 - 1 = 01−1=0。综上所述，让所有的情侣都能牵手至少须要交换的次数为
     *
     * (N_1 - 1) + (N_2 - 1) + \cdots + (N_n - 1) = (N_1 + N_2 + \cdots + N_n) - n = N - n
     * (N
     * 1
     * ​
     *  −1)+(N
     * 2
     * ​
     *  −1)+⋯+(N
     * n
     * ​
     *  −1)=(N
     * 1
     * ​
     *  +N
     * 2
     * ​
     *  +⋯+N
     * n
     * ​
     *  )−n=N−n
     *
     * 故「至少交换的次数 = 所有情侣的对数 - 并查集里连通分量的个数」。
     * 复杂度分析：
     *
     * 时间复杂度： O(N \log N)O(NlogN)，这里 NN 是输入数组的长度，O(\cfrac{N}{2} \log \cfrac{N}{2}) = O(N\log N)O(
     * 2
     * N
     * ​
     *  log
     * 2
     * N
     * ​
     *  )=O(NlogN) ；
     * 空间复杂度：O(N)O(N)，并查集底层使用的数组长度为 \cfrac{N}{2}
     * 2
     * N
     * ​
     *  ，O(\cfrac{N}{2})= O(N)O(
     * 2
     * N
     * ​
     *  )=O(N)。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/couples-holding-hands/solution/qing-lu-qian-shou-by-leetcode-gl1c/
     * @param row
     * @return
     */
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int N = n/2;
        UnionFind uf = new UnionFind(N);
        for(int i=0;i<n;i+=2){
            uf.union(row[i]/2,row[i+1]/2);
        }
        return N-uf.getCount();
    }

    class UnionFind{
        int[] parent;
        int count;

        UnionFind(int n){
            count = n;
            parent = new int[n];
            for(int i=0;i<n;i++){
                parent[i] = i;
            }
        }

        int find(int x){
            if(parent[x]!=x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x,int y){
            int newX = find(x);
            int newY = find(y);
            if(newX==newY){
                return;
            }
            parent[newY] = newX;
            count--;
        }

        int getCount(){
            return count;
        }
    }
}
